// 统计数组中最大的数
function ArrayMax(list){
   return  list.reduce((pre,cur)=>{
        if (cur>pre){
            return cur
        }
        return pre
    },-Infinity)
}

// console.log(ArrayMax([3,2,7,4]))




// 二分查找
function binarySearch(list,target){
    let left=0
    let right=list.length-1

    while (left<right){
        let mid=Math.floor((left+right)/2)

        if (list[mid]===target){
            return mid
        }else if(list[mid]<target){
            left=mid+1
        }else {
            right=mid-1
        }
    }

    return -1
}

// 冒泡排序 复杂度 o(n)
function bubbleSort(arr) {
    let len = arr.length;
    for (let i = 0; i < len ; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            // 比较相邻元素，‌如果顺序错误就交换
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

// 快排  B站视频：https://www.bilibili.com/video/BV1j841197rQ/?spm_id_from=333.337.search-card.all.click&vd_source=e46d9099be60057b5a16a45fac0d5248

function quickSort(arr, left, right) {

    if (left>=right){
        return
    }
    let pivotIndex= partition(arr, left, right)
    quickSort(arr, left, pivotIndex-1)
    quickSort(arr, pivotIndex+1, right)
}

function partition(arr,left,right){
    let l=left
    let r=right

    // 确定中间位置，基于中间位置不停左右交换
    let midIndex = Math.floor((l + r) / 2)
    let pivot = arr[midIndex]

    // 当左侧小于等于右侧则表示还有项没有对比，需要继续
    while (l <= r) {
        // 当左侧小于基准时查找位置右移，直到找出比基准值大的位置来
        while (l <= r && arr[l] < pivot) { // 当操作while条件中的变量时，必须加上while条件，否则会出现不符合最外层while的情况
            l++
        }
        // 当前右侧大于基准时左移，直到找出比基准值小的位置来
        while (l <= r && arr[r] > pivot) {
            r--
        }

        if(l <= r){
            // 数据交换，小的交换到基准左侧，大的交换到右侧
            [arr[l], arr[r]] = [arr[r], arr[l]]
            l++
            r--
        }

    }

    // arr[l]=pivot

    return l // 返回基准值
}

const arr= [3,2,5,1,6]
quickSort(arr,0,arr.length-1)
console.log(arr)
